#include "predictor.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>

using namespace std;

#pragma mark - COUNTERS.H 
// ---------------------------------------------------------------------------------------------------------------------
// COUNTERS.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __COUNTERS_H__
#define __COUNTERS_H__

using namespace std;
class counter2
{
public:
	uint bits:2;
    uint size;
	counter2()			:bits(3),size(2){};                                 // Default Constructor
	counter2(int val)	:bits(val){};
	counter2(char val)	:bits(val){};
	counter2(short val)	:bits(val){};
	counter2(uint val)	:bits(val){};

	counter2& operator++(int){if(bits<3)this->bits++; return *this;}    // Increment Counter 
	counter2& operator--(int){if(bits>0)this->bits--; return *this;}    // Decrement Counter
	bool   isTaken()	{ return bits & 0x2;}                           // Return the MSB
	string isTakenStr()	{ return (isTaken()) ? string("taken"):string("not taken");}
    friend ostream& operator<<(ostream& lhs, const counter2& rhs)       // Print
    {
        lhs << (bool)(rhs.bits & 0x2) << (bool)(rhs.bits & 0x1);
        return lhs;
    }
};

class counter3
{
public:
	uint bits:3;
    uint size;
	counter3()			:bits(7),size(3) {};                                   // Constructors 
	counter3(int val)	:bits(val){};
	counter3(char val)	:bits(val){};
	counter3(short val)	:bits(val){};
	counter3(uint val)	:bits(val){};
	string isTakenStr()	{ return (isTaken()) ? string("taken"):string("not taken");}
	counter3& operator++(int){if(bits<7)this->bits++; return *this;}    // Increment Counter
	counter3& operator--(int){if(bits>0)this->bits--; return *this;}    // Decrement Counter
	bool   isTaken()	{ return bits & 0x4;}                           // Return MSB
    friend ostream& operator<<(ostream& lhs, const counter3& rhs)       // Print
    {
        lhs << (bool)(rhs.bits & 0x4) << (bool)(rhs.bits & 0x2) << (bool)(rhs.bits & 0x1);
        return lhs;
    }
};
#endif 	// __COUNTERS_H__

#pragma mark - SHIFT_REGISTERS.H 
// ---------------------------------------------------------------------------------------------------------------------
// SHIFT_REGISTERS.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __SHIFT_REGISTERS_H__
#define __SHIFT_REGISTERS_H__

class shift_reg 						
{
public:
	uint bits;                                      // bool array for storing bits
	uint size; 										// size of the register
    uint mask;
    
	shift_reg(int len){  							// contructor with length as input
		bits = 0;                                   // Make the bool array of size len
		size = len; 								// set size of register to len
        mask = 1;                                   // mask = 0x1
        mask<<=size;                                // shift that 1 till it reaches bit size
        mask--;                                     // Decrement mask to get all ones (mask)
    }
    
    shift_reg(const shift_reg& reg){                
        this->size = reg.size;
        this->bits = reg.bits;
        this->mask = reg.mask;
    }
    
    shift_reg& operator= (const shift_reg& reg){
        if (this != &reg){
            this->size = reg.size;
            this->bits = reg.bits;
            this->mask = reg.mask;
        }
        return *this;
    }
    
	void push(bool bit){ 							// pushes bits in and calcs the value of the register
        bits<<=1;                                   // shift left by 1
        bits|=bit;                                  // or with the input bit to set LSB = input bit
        bits&=mask;                                 // apply mask 
    }
    
    friend ostream& operator<<(ostream& lhs, const shift_reg& rhs) 	// prints out the bits
    {																// e.g. usage: cout << reg << endl;
        uint m = 1<<(rhs.size-1);
        
        for (int i=rhs.size; i>0;i--){
            if (i%4 == 0) 
                lhs << " ";
			lhs << (bool)(rhs.bits & m); 
            m>>=1;
		}
        return lhs;
    }
};
#endif 	// __SHIFT_REGISTERS_H__

#pragma mark - LOCAL_HISTORY_TABLE.H 
// ---------------------------------------------------------------------------------------------------------------------
// LOCAL_HISTORY_TABLE.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __LOCAL_HISTORY_TABLE_H__
#define __LOCAL_HISTORY_TABLE_H__

#define DEFAULT_LOCAL_TABLE_SIZE 1024
#define DEFAULT_HISTORY_PATTERN_SIZE 10

using namespace std;

class local_history_table {
	vector<shift_reg> table;
public:
    uint size;
    uint table_length;

    uint pattern_width;

	local_history_table():table_length(DEFAULT_LOCAL_TABLE_SIZE),pattern_width(DEFAULT_HISTORY_PATTERN_SIZE)
    {
		for (uint i=0; i<table_length; i++)
            table.push_back(shift_reg(pattern_width));
        size = table_length*pattern_width;
    }
	local_history_table(uint length, uint width):table_length(length),pattern_width(width)
    {
		for (uint i=0; i<table_length; i++)
            table.push_back(shift_reg(pattern_width));
        size = table_length*pattern_width;
	}
    inline uint indexFor(uint pc)
    {
        return pc & (table_length - 1);             
    }
	shift_reg& operator[] (int pc){
		return table[indexFor(pc)];
	}
    void print()
    {
        for (uint i =0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

class local_prediction_table {
	counter3 *table;
public:
    uint table_length;
    uint size;

	local_prediction_table(){
		table = new  counter3[DEFAULT_LOCAL_TABLE_SIZE];
        table_length = DEFAULT_LOCAL_TABLE_SIZE;
        size = table_length*3;
	}
	local_prediction_table(int length):table_length(length){
		table = new  counter3[table_length];
        size = table_length*3;
	}
	~local_prediction_table(){
		delete table;
	}
    inline uint indexFor(uint indx)
    {
        return indx & (table_length - 1);
    }
	counter3& operator[] (int indx){
		return table[indexFor(indx)];
	}
    void print()
    {
        for (uint i=0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

#endif 	// __LOCAL_HISTORY_TABLE_H__

#pragma mark - GLOBAL_PREDICTION_TABLE.H 
// ---------------------------------------------------------------------------------------------------------------------
// GLOBAL_PREDICTION_TABLE.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __GLOBAL_PREDICTION_TABLE_H__
#define __GLOBAL_PREDICTION_TABLE_H__

#define DEFAULT_GLOBAL_TABLE_SIZE 4096

class global_prediction_table {
	counter2 *table;
public:
    uint table_length;
    uint size;
    
	global_prediction_table(){
		table = new  counter2[DEFAULT_GLOBAL_TABLE_SIZE];
        table_length = DEFAULT_GLOBAL_TABLE_SIZE;
        size = table_length * table[0].size;                // size in bits
	}
	global_prediction_table(int length):table_length(length){
		table = new  counter2[length];
        size = table_length * table[0].size;                // size in bits
	}
	~global_prediction_table(){
		delete table;
	}
    inline uint indexFor(uint indx)
    {
        return indx & (table_length - 1);
    }
	counter2& operator[] (uint indx){
		return table[indexFor(indx)];
	}
    void print()
    {
        for (uint i=0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

class choice_prediction {
	counter2 *table;
public:
    uint table_length;
    uint size;
    
	choice_prediction(){
		table = new  counter2[DEFAULT_GLOBAL_TABLE_SIZE];
        table_length = DEFAULT_GLOBAL_TABLE_SIZE;
        size = table_length * table[0].size;                // size in bits
	}
	choice_prediction(int length):table_length(length){
		table = new  counter2[length];
        size = table_length * table[0].size;                // size in bits
	}
	~choice_prediction(){
		delete table;
	}
    inline uint indexFor(uint indx)
    {
        return indx & (table_length - 1);
    }
	counter2& operator[] (uint indx){
		return table[indexFor(indx)];
	} 
    void print()
    {
        for (uint i=0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

#endif 	// __GLOBAL_PREDICTION_TABLE_H__

#pragma mark - PREDICTOR.CC 

// ---------------------------------------------------------------------------------------------------------------------
// PREDICTOR.cc
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------
//

#include <stdlib.h>

#define NOT_TAKEN 	0
#define TAKEN 		1

using namespace std;

/*
---------------------------------------------------------------------------------------------------------------------
OBJECTS & VARIABLES 
---------------------------------------------------------------------------------------------------------------------
*/

struct local_global_prediction {
    bool local_prediction;
    bool global_prediction;
    bool prediction;
};

#pragma mark - Variables 

uint print_counter = 0;

uint table_length = 512;                           // Local History Table Length
uint pattern_size = 10;                             // Local History Pattern Size
uint predictor_length = (uint)powf(2,pattern_size); // Local Predictor Length 
uint path_history_length = 12;                      // Path History Length
uint tb_length = 128;                               // Target Buffer Length
uint tb_sets = 4;                                   // Number of Target Buffer Sets
uint rs_depth = 64;                                 // R_stack depth

local_history_table     local_history(table_length, pattern_size);          // Local History Table (10-bit shift registers) 
local_prediction_table  local_predictor((uint)powf(2,pattern_size));        // Local Predictor Table (3-bit saturation counters)
shift_reg 			  	path_history(path_history_length);                  // Path History (12-bit shift register)
global_prediction_table global_predictor((uint)powf(2,path_history_length));// Global Predictor Table (2-bit saturation counters) 
choice_prediction 		prediction_chooser((uint)powf(2,path_history_length));  // Choice Prediction (2-bit saturation counters)
local_global_prediction last_prediction;                                    // 2 bits 

void print_tables()
{
    cout << "Local History Table (" << local_history.table_length << " x " << local_history.pattern_width << ")" << endl;
    local_history.print();
    cout << endl;
    cout << endl;
    cout << endl;
    cout << endl;
    cout << "Local Prediction Table (" << local_predictor.table_length << " x 3)" << endl;
    local_predictor.print();
    cout << endl;
    cout << endl;
    cout << "Global Prediction Table (" << global_predictor.table_length << " x 2)" << endl;
    global_predictor.print();
    cout << endl;
    cout << endl;
    cout << "Prediction Chooser Table (" << prediction_chooser.table_length << " x 2)" << endl;
    prediction_chooser.print();
    
}

void print_system_size()
{ 
    uint alpha_total_size = local_history.size + local_predictor.size + global_predictor.size + prediction_chooser.size + path_history.size + 3;
    cout << "*********************************************************" << endl;
    cout << "Alpha Predictor:" << endl;
    printf("Local History Table:               %8d x %2d = %8d bits\n", local_history.table_length, local_history.pattern_width,local_history.size);
    printf("Local Prediction Table:            %8d x %2d = %8d bits\n", local_predictor.table_length, 3,local_predictor.size);
    printf("Global Prediction Table:           %8d x %2d = %8d bits\n", global_predictor.table_length, 2, global_predictor.size);
    printf("Prediction Chooser Table:          %8d x %2d = %8d bits\n", prediction_chooser.table_length, 2,prediction_chooser.size);    
    printf("Path History:                      %8d x %2d = %8d bits\n", 1, path_history.size,path_history.size);    
    printf("Last Prediction:                   %8d x %2d = %8d bits\n", 1, 3, 3);    
    printf("-----------------------------------------------------------------\n");
    printf("Total Alpha Predictor Size                       = %8d bits\n",alpha_total_size);
    printf("                                                 = %8.2f kB\n",(float)alpha_total_size/1024/8);
    printf("Remaining Bits                                   = %8d bits\n", 64*1024 - alpha_total_size);
    cout << endl;    
}

/* 
---------------------------------------------------------------------------------------------------------------------
ALPHA BRANCH PREDICTOR - Refer to fig: 4 of "The Alpha 21264 microprocessor" paper for an illustrative description 
---------------------------------------------------------------------------------------------------------------------
BRANCH TARGET PREDICTION 
---------------------------------------------------------------------------------------------------------------------
*/
#pragma mark - Branch Predictor

void update_prediction_chooser(const branch_record_c *br, uint outcome)
{
    bool local_mispredict   = last_prediction.local_prediction != outcome;
    bool global_mispredict  = last_prediction.global_prediction != outcome;

    if (local_mispredict != global_mispredict) {
        if (local_mispredict)                       // if local mispredict
            prediction_chooser[path_history.bits]++; // Increment the counter towards global
        else                                        // if global mispredict
            prediction_chooser[path_history.bits]--; // Decrement the counter towards local 
    }
}

void update_global_branch_prediction(const branch_record_c *br, uint outcome){
    uint path_hist = path_history.bits;                          // Get the path_history
    if (outcome == TAKEN)                                       // If the outcome was Taken
        global_predictor[path_hist]++;                          // increment counter
    else                                                        // else if Not taken
        global_predictor[path_hist]--;                          // decrement counter
    
}

void update_local_branch_prediction(const branch_record_c *br, uint outcome){
    
    uint pc = br->instruction_addr;                             // Get the Current PC
    uint pattern = local_history[pc].bits;                       // Get the local history pattern at the index
    if (outcome == TAKEN)                                       // If the outcome is Taken
        local_predictor[pattern]++;                             // Increment the local_predictor counter
    else                                                        // If it is not taken
        local_predictor[pattern]--;                             // Decrement the local_predictor counter    
    
    local_history[pc].push(outcome);                            // push the outcome in the shift-register    
}

bool global_branch_prediction(const branch_record_c* br)
{
    uint path_hist = path_history.bits;                         // Extract the path_history    
    return global_predictor[path_hist].isTaken();                            // return the MSBit
}

bool local_branch_prediction(const branch_record_c* br)
{
    uint pc = br->instruction_addr;                             // Current PC    
    uint pattern = local_history[pc].bits;                      // The local history pattern at the indx 
    return local_predictor[pattern].isTaken();    
}

void update_branch_prediction(const branch_record_c *br, uint outcome)
{
    if (br->is_return) {
        return;
    }
    update_local_branch_prediction(br, outcome);                // Update local predictor
    update_global_branch_prediction(br, outcome);               // Update global predictor
    update_prediction_chooser(br, outcome);
        
    path_history.push(outcome);                                 // Update path history
}

bool alpha_branch_prediction(const branch_record_c* br)
{
    if (br->is_return) {
        last_prediction.local_prediction = TAKEN;               // Store the local prediction
        last_prediction.global_prediction = TAKEN;              // Store the global prediction
        last_prediction.prediction = TAKEN;                     // Store the prediction
        return TAKEN;
    }

    bool prediction = NOT_TAKEN;
	bool local_prediction 	= local_branch_prediction(br); 		// Get the local branch prediction
	bool global_prediction	= global_branch_prediction(br);    	// Get the global branch prediction 

    bool take_global_predictor = prediction_chooser[path_history.bits].isTaken();             // If the MSB is 1 then take global predictor.
    
    if (take_global_predictor)
        prediction = global_prediction;
    else 
        prediction = local_prediction;     

    last_prediction.local_prediction = local_prediction;        // Store the local prediction
    last_prediction.global_prediction = global_prediction;      // Store the global prediction
    last_prediction.prediction = prediction;                    // Store the prediction

	return prediction;
}	

/* 
---------------------------------------------------------------------------------------------------------------------
SIMULATOR INTERFACE 
---------------------------------------------------------------------------------------------------------------------
*/

bool PREDICTOR::get_prediction(const branch_record_c* br, const op_state_c* os, uint *predicted_target_address)
{
    print_counter++;
    if(print_counter == 1)
        print_system_size();
    bool prediction = alpha_branch_prediction(br);
    return prediction;
}

// Update the predictor after a prediction has been made.  This should accept
// the branch record (br) and architectural state (os), as well as a third
// argument (taken) indicating whether or not the branch was taken.
void PREDICTOR::update_predictor(const branch_record_c* br, const op_state_c* os, bool taken, uint actual_target_address)
{
    update_branch_prediction(br, taken);   
}  